Authenticating techniques have been utilized to confirm the identity of a user. One of the authenticating techniques is the challenge and response authentication employing the secret key encryption scheme. In the challenge and response authentication, the same key has been previously shared with an authentic authenticatee apparatus owned by the user and an authenticator apparatus authenticating the authentic authenticatee apparatus (hereinafter, referred to as a shared key). Then, when authenticating the authenticatee apparatus, the authenticator apparatus sends the authenticatee apparatus random numbers as challenge information. The authenticatee apparatus encrypts, using the shared key, the received challenge information as a message. Then, the authenticatee apparatus returns the encrypted message to the authenticator apparatus as response information. The authenticator apparatus decrypts the received response information, using the same shared key. Thus, the authenticator apparatus confirms whether or not the decrypted message matches with the initially sent challenge information. In the case where the decrypted message matches with the initially sent challenge information, the authenticator apparatus judges that the authenticatee apparatus obtains the previously shared key, and that the user who owns the authenticatee apparatus is authentic. This enables the authenticator apparatus to confirm the identity of the user.
However, in the case where the previously shared key is revealed to a third person in the above described challenge and response authentication, the third person can masquerade as the authentic user of the authenticatee apparatus. One of the causes of the revealed shared key is insufficient tamper-resistant implementation on an authenticatee apparatus, holding a secret shared key, such as a user terminal and an IC card. Here, an unauthorized access to the authenticatee apparatus causes a secret shared key to be revealed. As a solution to the problem, Patent Reference 1 has disclosed a technique to execute the challenge and response authentication, using the Physical Unclonable Function (referred to as the PUF, hereinafter) (Paragraphs 0061 to 0076 in Patent Reference 1).
Fine chip-to-chip variations in physical characteristics are observed even though the chips are produced out of the same mask. The PUF technique, taking advantage of the fine variations for generating chip unique information, is utilized for a chip unique identifier and a chip unique key. A circuit produced based on the PUF technique (referred to as a PUF circuit, hereinafter), as a function, receives input data and outputs output data corresponding to the input data. In the challenge and response authentication utilizing the PUF circuit, first, the authenticator apparatus has, in advance, initially registered output data of an authentic authenticatee apparatus, using the authentic authenticate apparatus including the PUF circuit. In other words, the authenticator apparatus obtains and stores the input data of the PUF circuit and the corresponding output data thereto. Then, the authenticatee apparatus is given to the user, the authenticatee. When authenticating, the authenticator apparatus sends the authenticatee apparatus a piece of pre-obtained input data of the PUF circuit as the challenge information. The authenticatee apparatus inputs the received challenge information into the PUF circuit as the input data, and obtains the output data of the PUF circuit. Then, the authenticatee apparatus returns the output data to the authenticator apparatus as the response information. The authenticator apparatus confirms whether or not the received response information and the output data corresponding to the initially sent input data corresponds. In the case where the received information matches with the output data, the authenticator apparatus judges that the authenticatee apparatus is an authentic apparatus, and thus the user who owns the authenticatee apparatus is authentic.
A feature of the PUF circuit is to make production of another clone circuit having the same physical characteristics (PUF chip) difficult since the PUF circuit takes advantage of the fine chip-to-chip variations in physical characteristics. A use of the PUF circuit for authentication solves a problem for the above described challenge and response authentication; that is, a problem that the leaked secret key allows the third person to masquerade. To implement the PUF circuit in the Patent Reference 1, the chip unique information is generated, focusing on chip-to-chip differences in wiring of a semiconductor circuit and propagation delay of a part of the semiconductor circuit. Specifically, the PUF circuit includes plural paths passing through different wirings and parts. Then, the PUF circuit uniquely selects two of the above plural paths in the semiconductor circuit based on the input data, compares propagation delays between the two paths, and generates a chip unique value (a value of 1 bit, for example) depending on which path causes a longer delay.
It is known, however, that a propagation delay of each of the paths in the PUF circuit varies depending on variations of a temperature of the PUF circuit (a surface temperature and an external temperature) and an amount of a supply voltage to the PUF circuit. Accordingly, even though the same input data is inputted in the same PUF circuit, the output data possibly changes in the case where the temperature of the PUF circuit and the amount of the supply voltage to the PUF circuit vary. The theory works as follows.
First, two paths (path 1 and path 2) are assumed to be selected when the PUF circuit receives the same input data. Here, under a first environment (temperature and supply voltage), the path 1 causes a longer propagation delay than the path 2 does. As a result, the PUF circuit outputs, for example, a unique bit indicating 1. Meanwhile, under a second environment which is different from the above first environment, a magnitude correlation between the path 1 and the path 2 may reverse when the same PUF circuit receives the same input data, and the path 2 may cause a longer propagation delay than the propagation delay of the path 1. In this case, the PUF circuit outputs a different unique bit, from the initial unique bit, indicating 0.
As described above, the PUF circuit possibly outputs different output data depending on an environmental change even though the same input data is inputted in the same PUF circuit. Such a case may cause the authenticator apparatus to falsely recognize the authentic user as an unauthorized user.
Hence, the Patent Reference 1 has overcome the problem, focusing on the fact that the magnitude correlation between the paths 1 and 2 does not reverse despite a more or less environmental change (temperature and amount of supply voltage) in the case where the propagation delays between the paths 1 and 2 are considerably different. Specifically, the authenticator apparatus previously comprehends input data allowing paths 1 and 2 having propagation delays significantly different each other to be selected. Only such input data does the authenticator apparatus use in the challenge and response authentication (paragraph numbers 0107 to 0112 in Patent Reference 1).    [Patent Reference 1] US 2003/0204743